package psn.zjk.career.interview.algorithm;

/**
 * @Description 编写一个函数来查找字符串数组中的最长公共前缀。
 * <p>
 * 如果不存在公共前缀，返回空字符串 ""。
 * <p>
 * 示例 1：
 * <p>
 * 输入：strs = ["flower","flow","flight"]
 * 输出："fl"
 * <p>
 * 来源：力扣（LeetCode4）
 * 链接：https://leetcode-cn.com/problems/longest-common-prefix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @User zero
 * @Datetime 2021/5/9 12:00
 */
public class LeetCode14 {

    //解法1：两两比较
    //解法2：纵向比较，从前往后一列列比较
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        StringBuilder prefix = new StringBuilder();
        char c = 0;
        A:
        for (int i = 0; i < strs[0].length(); i++) {
            c = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                if (strs[j].length() == i || strs[j].charAt(i) != c) {
                    break A;
                }
            }
            prefix.append(c);
        }

        return prefix.toString();
    }

    //解法3：分治
    public String longestCommonPrefix3(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        } else {
            return prefix(strs, 0, strs.length - 1);
        }
    }

    private String prefix(String[] strs, int left, int right) {
        if (left == right) {
            return strs[left];
        } else {
            int mid = strs.length / 2;
            String part1 = prefix(strs, 0, mid);
            String part2 = prefix(strs, mid + 1, right);
            return commonPre(part1, part2);
        }
    }

    private String commonPre(String str1, String str2) {
        int min = Math.min(str1.length(), str2.length());
        for (int i = 0; i < min; i++) {
            if (str1.charAt(i) != str2.charAt(i)) {
                return str1.substring(0, i);
            }
        }
        return str1.substring(0, min);
    }

    public static void main(String[] args) {
        String s = new LeetCode14().longestCommonPrefix(new String[]{"flower", "flow", "flight"});
        System.out.println(s);

    }

}
